import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-01-22
 * Time: 17:02
 */
class Card{
    public int rank;//数值
    public String suit;//
    public Card(int rank,String suit){
        this.rank=rank;
        this.suit=suit;
    }

    public int compareTo(Card o){
        return this.rank-o.rank;
    }

    public String toString(){
        return "Card{"+"rank="+rank+",suit="+suit+'\''+'}';
    }


}

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem=new int[10];
    }
    //以大堆为例——如果换小堆，把shiftDown里面的<换成>即可
    public void shiftDown(int parent,int len){
        //parent:每棵树的根节点
        //len:每棵树的调整的结束位置
        int child=2*parent+1;//已知parent求左孩子公式
        //至少有一个（左）孩子
        //因为堆是完全二叉树，没有左孩子就一定没有右孩子，所以判断是否有左孩子
        while(child<len){
            if(child+1<len&&elem[child]<elem[child+1]){
                //child+1，比如10个孩子，孩子最大下标是9
                child++;//保证当前左右孩子最大值的下标
            }
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    public void createHeap(int[]array){
        for(int i=0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
            //usedSize是当前存储的节点个数，
            //第一次-1是：数组下标从0开始，最后一个节点下标是usedSize-1
            //第二次-1是：已知孩子求双亲下标公式：双亲(parent)下标 = (child - 1) / 2;

            //调整
            shiftDown(parent,usedSize);
        }
    }



    public void shiftUp(int child){//向上调整
        int parent=(child-1)/2;
        while(child>0){
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

    public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=val;
        shiftUp(usedSize-1);//注意这里传入的是usedSize-1
    }

    public boolean isFull(){
        return usedSize==elem.length;
    }


    //出队列：每次出队列保证出的是最大值/最小值
    //第一步：交换0下标和最后一个下标元素
    //第二步：调整0下标这棵树（向下调整）
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }

    public boolean isEmpty(){
        return usedSize==0;
    }


    //堆排序：
    //1：调整为大根堆-最上面元素是最大的
    //2：0下标和最后1个未排序元素交换（用end标记最后一个元素），交换后调整为大根堆
    //3.end--
    public void HeapSort(){
        int end=this.usedSize-1;//总节点数为usedSize，最后一个元素下标为usedSize-1
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            //先调整，再end--
            shiftDown(0,end);
            end--;
        }

    }

   /* public static void main(String[] args) {
        int[]array={27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap=new TestHeap();

        //创建大根堆
        testHeap.createHeap(array);
        //调试发现,testHeap里面的elem为：
        //[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]
        //摆成完全二叉树，正是我们所需要的

        testHeap.HeapSort();
        System.out.println("=====");

    }*/


    /*public static void main(String[] args) {
        int[]array={27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap=new TestHeap();

        //创建大根堆
        testHeap.createHeap(array);
        //调试发现,testHeap里面的elem为：
        //[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]
        //摆成完全二叉树，正是我们所需要的


        testHeap.offer(100);
        System.out.println("=====");

        int ret=testHeap.poll();
        System.out.println(ret);//弹出100

        ret=testHeap.poll();
        System.out.println(ret);//继续弹出当前队中最大元素——65
    }*/


    //优先级队列
    /*public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        //执行完上面代码，你就会有一个堆
        //但这个堆是大堆还是小堆不确定,需要你自己验证

        //PriorityQueue每放入一个元素，都会自己保证是大堆/小堆（元素位置会自己移动）
        priorityQueue.offer(12);
        priorityQueue.offer(3);
        priorityQueue.offer(15);
        System.out.println(priorityQueue.peek());//打印3，说明是小堆
        //到这里我们知道了，PriorityQueue默认是小堆

        System.out.println(priorityQueue.poll());//弹出元素的时候，也会保证是小堆
    }*/


    //优先级队列，向其中添加我们自己创建的类


    public static void main(String[] args) {
        Card card1=new Card(1,"♠");
        Card card2=new Card(2,"♥");
        PriorityQueue<Card> priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(card1);//运行没有问题

        //虽然说入队会保证大堆/小堆（自动比较），但是不管你屏不屏蔽上一行代码
        //priorityQueue.offer(null);//往里面放null就会报警告-空指针异常

        //priorityQueue.offer(card2);
        // 这里添加也会报警告，你自定义的类电脑不知道怎么比较大小，如果需要比较，你要自己弄一个比较方法
        //System.out.println(priorityQueue);//直接打印会报警告

        //我们在Card类里面自己写了一个compareTo方法
        System.out.println(card1.compareTo(card2));//
        System.out.println(card2.compareTo(card1));


        //对象的比较
        Card card3=new Card(1,"♠");//我们这里弄一张和card1一样的牌
        System.out.println(card1.equals(card3));//打印false
        //因为我们这里没有自己写equals，所以调用的是Object的方法，比较的是两者的地址

        //如果要比较，同样的，重写equals方法

        //覆写的方法：
        //1.Object.equals:
        //因为所有类都是继承自Object的，所以直接覆写即可，不过只能比较相等也否

        //2.Comparable.compareTo:
        //需要手动实现接口，且对类的侵入性比较强，但一旦实现，每次用该类都有顺序，属于内部顺序

        //3.Comparator.compare:
        //需要实现一个比较器对象，对待比较类的侵入性弱，但对算法代码实现侵入性强
    }
}
